1. Field of the Invention
The present invention relates to a method and to apparatus for the exponentiation of large binary numbers in a residue class modulo N. particularly for encoding and decoding digitally represented messages, wherein the exponentiation comprises repeated squaring/multiplication cycles having respective remainder formation.
2. Description of the Prior Art
By the representation of messages, particularly speech, in the field of telephone switching and telephone transmission technology, for example in so-called packet switching and transmission devices, the simple possibility exists per se of encoding the digital message at the transmission side, transmitting the message in encoded form, and decoding the message at the receiving side, whereby the message can be protected against eavesdropping.
Methods for encoding digital messages are already known in the art. For this purpose, for example, an encoding method having an underlying encoding algorithm has been proposed, along with other proposals, in the publication Elektronisch Rechenanlagen, Vol. 22, 1980, No. 6, pp. 276-280, H. Lagger, C. Muller, H. Unterberger: "Sicherheitsaspekte in rechnergesteuerten Kommunikationssystemen", by means of which the message blocks to be formed, which basically represent large binary numbers, are encoded and decoded by a complicated conversion process.
The execution of such methods has heretofore been generally carried out by program-controlled computers. Such a solution, however, has the disadvantage that it has a long processing time due to its inherent complexity, so that an operation of an arrangement for the execution of the method does not permit a real time processing as necessary, for example, for the transmission of speech. On the contrary, such arrangements are exclusively suited for processing and transmitting messages which are not subject to the real time condition such as, for example, text, data of various types to be evaluated over a long interval, etc.
The high time expense which encumbers known arrangements is essentially to be attributed to the fact that the appertaining algorithm must be, for an effective encoding which offers high secrecy protection, respectively applied to a large plurality of binary places which are to be encoded in a message block. The known R.S. A. algorithm, cf. Electronische Rechenanlagen, Vol. 22, 1980, No. 6, essentially provides that the message to be encoded is exponentiated with a specific key having a subsequent remainder formation, whereby the remainder formation is carried out by a division by a fixed number. The exponentiation is based on multiplication processes. The residue formation can respectively occur after each multiplication operation.
In the known encoding methods, the multiplication operations, the multiplication operations and the residue formation operations are sequenced in chronological succession which, among other things, is based on the fact that the appertaining operations are sequenced by a digital computer which executes the operations successively in successive computer cycles.